from debug import *
from buffer import *
from resource import *
from DAG import *
#from define_task4 import *
from class_task import *

dirty_time = 0
hit_time = 0

#排列关键资源
class CRL_node():
    def __init__(self) -> None:
        self.DAG = None #属于哪个任务，指向这个阶段所属的DAG
        self.DAG_node = None #保存这个node的DAG节点
        self.stage_id = 0 #是这个DAG的第几个阶段，存储DAG中node的id
        self.depen = 0 #依赖度，用于排序

        self.page = -1 #用于调整次序以命中
        self.die = -1
        self.time = 0 #保存运行时间，调整次序和alignment的时候要用

        self.next = None #指向下一个节点
        self.pre = None 

class CRL():
    def __init__(self,resource_name) -> None:
        #先创建一个depen很大的作为头节点，所以的节点都会插在他后面
        head_node = CRL_node()
        head_node.depen = 0xFFFFFFFF

        self.head = head_node
        self.resource_name = resource_name

        self.SOD = 0 #这个CRL的节点的depen值之和(Sum Of Depen)
        self.total_execution_time = 0

    # 插入一个节点
    def insert(self,node):    
        current_node = self.head #只定会小于或者等于这个Node
        while True:
            #判断是否还有下一个节点，没有的话就插在末尾
            if current_node.next == None: #说明遍历到最后一个节点都没找到，那就插在末尾
                current_node.next = node
                node.pre = current_node
                self.SOD += node.depen
                return

            #如果大于后一个节点，说明找到位置了（因为肯定小于current_node）
            if current_node.next.depen <= node.depen:
                #后一个节点先指向它
                current_node.next.pre = node
                #这个节点再指过来
                node.next = current_node.next
                node.pre = current_node
                #当前节点再指向它
                current_node.next = node
                self.SOD += node.depen
                return
                
            #如果后面还有节点并且还小于他，说明该继续往后找
            current_node = current_node.next

    def __str__(self) -> str:
        ret = ""
        current_node = self.head
        while current_node!=None:
            ret += '('
            if current_node.DAG == None:
                ret += "head"
            else:
                ret += current_node.DAG.name
            ret += ","
            ret += str(current_node.stage_id)
            ret += ","
            ret += str(current_node.depen) 
            ret += ","
            ret += str(current_node.time) 
            ret += ","
            ret += str(current_node.die) 
            ret += ","
            ret += str(current_node.page) 
            ret += ') '
            current_node = current_node.next
        return ret

    # 调整以增加命中率
    # 基本思想是向前找，如果能找到一个会命中的那么就看位置（找的时候要看是否对这个stage有依赖）
    # 调换的时候是调换到命中节点的后面第buffer_size个节点（减少对之前排好的序的影响）
    # 如果产生这次调换，那么向前插入的距离是回溯次数-buffer_size，然后向前距离*depen是否小于time
    def adjustment(self,buffer_size):
        #如果不是nfc那也不需要调整了
        if not "nfc" in self.resource_name:
            return

        #第一个节点没必要看了
        current_node = self.head.next
        while current_node != None: #一次循环处理一个节点
            next_node = current_node.next #先把下一个保存起来，因为等会current_node可能会变换位置
            
            #向前找
            recall = 1 #往前找了多少次了
            pre_node = current_node.pre
            while pre_node.die != -1:
                #如果找到命中的这个节点
                if pre_node.die == current_node.die and pre_node.page == current_node.page:
                    #先看看是否本来就能命中
                    if recall <= buffer_size:
                        break

                    #如果本来不能命中，那找到应当插入的位置
                    victim_node_count = recall-buffer_size #会有多少个node被推后
                    if current_node.time >= victim_node_count*current_node.depen: #如果本来判断一下是否交换，如果交换的话前面的每个任务可能会被推后current_node.depen的时间
                        #Get被插在后面的节点
                        victim_node = current_node
                        should_stop = False
                        for i in range(victim_node_count+1):
                            victim_node = victim_node.pre
                            #如果这个是它的父节点并且还需要往前面找那就不用看了
                            if victim_node.DAG == current_node.DAG:
                                dag = current_node.DAG
                                if dag.is_parent(victim_node.stage_id,current_node.stage_id) and i!=victim_node_count:
                                    should_stop = True

                        if should_stop:
                            break

                        #将current_node从当前节点抽离
                        current_node.pre.next = current_node.next 
                        if current_node.next != None: #如果这个节点后面还有
                            current_node.next.pre = current_node.pre

                        #将current_node插入到victim_node之后
                        current_node.next = victim_node.next
                        current_node.next.pre = current_node
                        victim_node.next = current_node
                        current_node.pre = victim_node

                    #只要找到命中的，不管交没交换都应该去下一个节点了,因为这次都没交换成功说明开销已经不划算了，再找的话被推迟的开销只会越来越大
                    break

                # #如果这个是它的父节点那也就不用找了
                # if pre_node.DAG == current_node.DAG:
                #     dag = current_node.DAG
                #     if dag.is_parent(pre_node.stage_id,current_node.stage_id):
                #         break

                pre_node = pre_node.pre
                recall += 1

            current_node = next_node

    def set_true_time(self,buffer_size):
        #不是nfc你来凑什么热闹
        if not 'nfc' in self.resource_name:
            return

        buffer = Buffer(buffer_size)
        current_node = self.head.next
        while current_node != None:
            if buffer.is_hit(current_node.page):
                global hit_time
                hit_time += 1
                current_node.time = 0
                current_node.DAG_node.time = 0
            else:
                clean = buffer.allocate(current_node.page)
                if not clean:
                    global dirty_time
                    dirty_time += 1
                    current_node.time += write_back_time
                    current_node.DAG_node.time = current_node.time
            #如果这是个写操作，那么需要置脏页
            if '写' in current_node.DAG.name or 'Write' in current_node.DAG.name:
                buffer.mark_dirty(current_node.page)

            #统计下执行时间
            self.total_execution_time += current_node.time

            current_node = current_node.next

MAX = 0xFFFFFFFFFFFFFFFF
#时间片链表(TimeLine List)
class TLL_node():
    def __init__(self,start=0,end=0) -> None:
        self.start_time = start
        self.end_time = end
        self.DAG_node = None #存储一个DAG Node
        self.next = None
        self.pre = None

class TLL():
    def __init__(self,resource_name) -> None:
        self.resource_name = resource_name
        #free_list要特别处理
        start_node = TLL_node(0,0)
        next_node = TLL_node(0,MAX)
        start_node.next = next_node
        next_node.pre = start_node

        self.free_list = start_node#自由时间片
        self.allocate_list = TLL_node(0,0) #已分配的时间片
        self.allocate_list_total_time = 0

    def __str__(self) -> str:
        ret = ""
        ret += self.resource_name
        
        ret += "\n    free_list:"
        temp = self.free_list
        while temp!=None:
            ret += "("
            ret += str(temp.start_time)
            ret += ','
            ret += str(temp.end_time)
            ret += ") "
            temp = temp.next

        ret += "\n    allocate_list:"
        temp = self.allocate_list
        while temp!=None:
            ret += "("
            ret += str(temp.start_time)
            ret += ','
            ret += str(temp.end_time)
            ret += ") "
            temp = temp.next

        return ret

    #只会从free_list中删除
    def delete_node(self,tll_node):
        #别把头节点给删了
        if tll_node == self.free_list or tll_node == self.allocate_list:
            return

        #如果没有前置节点
        if tll_node.pre == None:
            #也没有后置节点，也就是说就这一个节点
            if tll_node.next == None:
                self.free_list = None
            
            #有后置没前置
            else:
                tll_node.next.pre = None
                self.free_list = tll_node.next

        #有前置没后置（没前没后的已经处理了）
        elif tll_node.next == None:
            tll_node.pre.next = None

        else: #有前有后
            tll_node.pre.next = tll_node.next
            tll_node.next.pre = tll_node.pre

        #把这个节点的指针清空
        tll_node.pre = None
        tll_node.next = None

    
    #根据时间片的空隙把node插入进去
    def insert_node(self,head_node,tll_node):
        #统计平均时延
        if head_node == self.allocate_list:
            self.allocate_list_total_time += tll_node.end_time - tll_node.start_time

        current_node = head_node
        while current_node != None:
            #如果开始时间大于等于当前节点的结束时间
            if tll_node.start_time >= current_node.end_time:
                #如果没有后续节点了，就插在后面
                if current_node.next == None:
                    current_node.next = tll_node
                    tll_node.pre = current_node
                    return

                #如果还有后续节点，检查结束时间是否小于等于后面节点的开始时间
                if current_node.next.start_time >= tll_node.end_time:
                    current_node.next.pre = tll_node
                    tll_node.next = current_node.next
                    tll_node.pre = current_node
                    current_node.next = tll_node
                    return

            current_node = current_node.next

    def insert_pre_stage(self,dag_node,tll_dict):
        for pre_stage_id in dag_node.pre:
            if pre_stage_id != 0:
                pre_stage_node = dag_node.DAG.node_list[pre_stage_id-1]
                #如果没有完成那么先插入前置任务
                if pre_stage_node.finish_time == -1:
                    unit_name = pre_stage_node.unit
                    if unit_name in tll_dict: #如果是固定资源
                        tll = tll_dict[unit_name]
                        tll.insert_dagnode(pre_stage_node,tll_dict)

                    else: #如果是不固定的资源（例如matcher）
                        shortest_start_time = MAX
                        shortest_start_tll = None
                        
                        #找到所有的相关资源然后尝试分配找到一个最短的
                        for tll_unit in tll_dict:
                            if unit_name in tll_unit:
                                tll = tll_dict[tll_unit]
                                time = tll.try_insert_dagnode(pre_stage_node,tll_dict)
                                if time < shortest_start_time:
                                    shortest_start_time = time
                                    shortest_start_tll = tll

                        shortest_start_tll.insert_dagnode(pre_stage_node,tll_dict)

    #不做真正的插入，只是看看如果在这里插入的话开始时间是多久（用于平行机插入的方法）
    def try_insert_dagnode(self,dag_node,tll_dict):
        if dag_node.finish_time != -1:
            return dag_node.finish_time

        #还是先插入所有前置节点
        self.insert_pre_stage(dag_node,tll_dict)

        time = 0 #最早开始时间
        for pre_stage_id in dag_node.pre:
            if pre_stage_id != 0:
                pre_stage_node = dag_node.DAG.node_list[pre_stage_id-1]
                #获取完成时间
                if pre_stage_node.finish_time > time:
                    time = pre_stage_node.finish_time

        run_time = dag_node.time
        free_list_node = self.free_list
        while free_list_node != None:
            if free_list_node.end_time-free_list_node.start_time >= run_time: #首先时间片要足够长
                #如果是包含的情况
                if free_list_node.start_time <= time and free_list_node.end_time >= time+run_time:
                    return time

                if free_list_node.start_time > time:
                    return free_list_node.start_time

            free_list_node = free_list_node.next

        return time

    def insert_dagnode(self,dag_node,tll_dict,pre_node_in_crl=None):
        if dag_node.finish_time != -1:
            return

        #还是先插入所有前置节点
        self.insert_pre_stage(dag_node,tll_dict)

        time = 0 #最早开始时间
        for pre_stage_id in dag_node.pre:
            if pre_stage_id != 0:
                pre_stage_node = dag_node.DAG.node_list[pre_stage_id-1]
                #获取完成时间
                if pre_stage_node.finish_time > time:
                    time = pre_stage_node.finish_time

        #获取运行时间
        run_time = dag_node.time

        #如果运行时间为0，那么就直接插入allocate list了，因为可能free_list中并没有空闲时间片
        if run_time == 0:
            if pre_node_in_crl != None:
                time = max(time,pre_node_in_crl.finish_time)
            temp_node = TLL_node(time,time)
            temp_node.DAG_node = dag_node
            self.insert_node(self.allocate_list,temp_node)
            dag_node.finish_time = time
            return

        #(time,run_time)

        #到这里所有前置任务都完成了，可以开始插入这个node了
        #找到一个空闲时间片，要满足1.时间片包含了time 2.time+dag < 空闲时间片末尾
        free_list_node = self.free_list
        while free_list_node != None:
            #如果是包含的情况
            if free_list_node.start_time <= time and free_list_node.end_time >= time+run_time:
                #先把这个节点取出来
                self.delete_node(free_list_node)
                if free_list_node == self.free_list:
                    free_list_node = TLL_node(0,0)

                #如果时间正好一致那直接插入即可
                if free_list_node.end_time - free_list_node.start_time == run_time:
                    free_list_node.DAG_node = dag_node
                    self.insert_node(self.allocate_list,free_list_node)
                    dag_node.finish_time = free_list_node.end_time
                    return

                # 如果需要把free_list_node分裂成两个
                # 开始时间与节点一致
                if free_list_node.start_time == time:
                    end_time = free_list_node.end_time
                    free_list_node.end_time = time+run_time
                    free_list_node.DAG_node = dag_node
                    self.insert_node(self.allocate_list,free_list_node)
                    #创建剩余时间片然后还给自由时间链表
                    new_node = TLL_node(time+run_time,end_time)
                    self.insert_node(self.free_list,new_node)

                    dag_node.finish_time = free_list_node.end_time
                    return

                # 完成时间与节点一致
                elif free_list_node.end_time == time+run_time:
                    start_time = free_list_node.start_time
                    free_list_node.start_time = time
                    free_list_node.DAG_node = dag_node
                    self.insert_node(self.allocate_list,free_list_node)
                    new_node = TLL_node(start_time,time)
                    self.insert_node(self.free_list,new_node)

                    dag_node.finish_time = free_list_node.end_time
                    return

                #如果是从中间分裂，需要分裂成3个
                else:
                    #保存原本的起止时间
                    start_time = free_list_node.start_time
                    end_time = free_list_node.end_time

                    free_list_node.start_time = time
                    free_list_node.end_time = time+run_time
                    free_list_node.DAG_node = dag_node
                    self.insert_node(self.allocate_list,free_list_node)

                    #创建额外的2个节点
                    new_node = TLL_node(start_time,time)
                    self.insert_node(self.free_list,new_node)
                    new_node = TLL_node(time+run_time,end_time)
                    self.insert_node(self.free_list,new_node)

                    dag_node.finish_time = free_list_node.end_time
                    return

            #如果是不包含的情况
            if (free_list_node.start_time >= time) and (free_list_node.end_time-free_list_node.start_time >= run_time):
                #先把这个节点取出来
                self.delete_node(free_list_node)

                #如果执行时间正好相等
                if free_list_node.end_time-free_list_node.start_time == run_time:
                    free_list_node.DAG_node = dag_node
                    dag_node.finish_time = free_list_node.end_time
                    return

                #起点超过了time，时间片长度也大于总时间
                else:
                    new_node = TLL_node(free_list_node.start_time + run_time,free_list_node.end_time)
                    self.insert_node(self.free_list,new_node)

                    free_list_node.end_time = free_list_node.start_time + run_time
                    free_list_node.DAG_node = dag_node
                    self.insert_node(self.allocate_list,free_list_node)

                    dag_node.finish_time = free_list_node.start_time + run_time
                    return

            #如果没找到，去往下一个时间片
            free_list_node = free_list_node.next
        
def alg(tasks,resource):
    global dirty_time
    global hit_time
    dirty_time = 0
    hit_time = 0
    #将DAG图初始化后作为task的成员
    for task in tasks.task_list:
        task.DAG = DAG(task)

    #为每个resource创建一个CRL
    CRL_dict = {}
    CRL_dict["matcher"] = CRL("matcher") #为matcher专门创建一个（写得太挫了！）,因为请求的里面的单元是matcher而resource里面是写的mather1/2
    for unit_name in resource:
        if "matcher" in unit_name:
            continue
        CRL_dict[unit_name] = CRL(unit_name)

    #遍历所有的任务的所有stage，将任务添加到相应的CRL中
    for task in tasks.task_list:
        dag = task.DAG #获取每个任务的DAG
        for stage in dag.node_list:
            #创建这个stage相应的节点
            node = CRL_node()
            node.DAG = dag
            node.DAG_node = stage
            node.stage_id = stage.id
            node.depen = stage.depen
            node.time = stage.time
            node.page = stage.page
            node.die = stage.die

            crl = CRL_dict[stage.unit] #获取相应的crl对象
            crl.insert(node) #插入crl

    # #打印crl看看
    # print("Format:task,stage,CPD,time,die,page")
    # for crl in CRL_dict:
    #     print(crl,CRL_dict[crl].SOD,CRL_dict[crl])

    #调整以命中
    total_execution_time = 0
    for crl in CRL_dict:
        CRL_dict[crl].adjustment(buffer_size)
        CRL_dict[crl].set_true_time(buffer_size)

        #找到最长执行时间
        total_execution_time = max(total_execution_time,CRL_dict[crl].total_execution_time)

    #打印crl看看
    # print("Format:task,stage,CPD,time,die,page")
    # for crl in CRL_dict:
    #     print(crl,CRL_dict[crl].SOD,CRL_dict[crl])

    #为每个资源创建一个TLL（每个具体器件都有一个）
    TLL_dict = {}
    for unit_name in resource:
        TLL_dict[unit_name] = TLL(unit_name)

    #迭代找到时间最长的crl
    for crl_count in range(len(CRL_dict)):
        max_crl_this_turn = None
        max_crl_value = 0
        for crl in CRL_dict:
            if CRL_dict[crl].SOD >= max_crl_value:
                max_crl_value = CRL_dict[crl].SOD
                max_crl_this_turn = CRL_dict[crl]

        #print("max_crl_this_turn",max_crl_this_turn.resource_name)

        #标记一下是不是nfc任务，是的话在插入每个节点后把后面的那个任务一块插了
        is_nfc = False
        if "nfc" in max_crl_this_turn.resource_name:
            is_nfc = True

        #依次取出node然后放入相应的TLL中
        current_node = max_crl_this_turn.head.next
        while current_node!=None:
            if current_node.DAG_node.finish_time != -1:
                current_node = current_node.next
                continue

            unit_name = current_node.DAG_node.unit
            if unit_name in TLL_dict: #如果是固定资源
                tll = TLL_dict[unit_name]
                tll.insert_dagnode(current_node.DAG_node,TLL_dict,current_node.pre.DAG_node)
                #如果是NFC，把后面的arm任务一块插了
                if is_nfc:
                    next_dag_node = current_node.DAG.node_list[current_node.DAG_node.sub[0]-1]
                    tll.insert_dagnode(next_dag_node,TLL_dict)

            else: #如果是不固定的资源（例如matcher）
                shortest_start_time = MAX
                shortest_start_tll = None
                
                #找到所有的相关资源然后尝试分配找到一个最短的
                for tll_unit in TLL_dict:
                    if unit_name in tll_unit:
                        tll = TLL_dict[tll_unit]
                        time = tll.try_insert_dagnode(current_node.DAG_node,TLL_dict)
                        if time < shortest_start_time:
                            shortest_start_time = time
                            shortest_start_tll = tll

                shortest_start_tll.insert_dagnode(current_node.DAG_node,TLL_dict)

            current_node = current_node.next

        max_crl_this_turn.SOD = -1

    # #打印当前的TLL，看看调度方案
    # for tll_unit in TLL_dict:
    #     tll = TLL_dict[tll_unit]
    #     print(tll)

    #alignment结束后找到结束时间最晚的即可
    max_allocate_time = 0
    for tll_name in TLL_dict:
        tll = TLL_dict[tll_name]
        tmp_node = tll.allocate_list
        while tmp_node!=None:
            max_allocate_time = max(max_allocate_time,tmp_node.end_time)
            tmp_node = tmp_node.next

    #统计下平均时延
    avg_time = 0
    for task in tasks.task_list:
        dag = task.DAG #获取每个任务的DAG
        avg_time += dag.node_list[-1].finish_time

    #统计平均在忙资源数
    sampling_interval = 100
    should_count = int(max_allocate_time/sampling_interval)*len(resource) #应该采样到多少次
    count = 0 #实际采样到多少次
    for tll_name in TLL_dict:
        tll = TLL_dict[tll_name]
        tmp_node = tll.allocate_list
        while tmp_node!=None:
            #看看这个节点包含了多少个100的整数倍
            if tmp_node.start_time%sampling_interval == 0:
                count += 1
            if tmp_node.end_time%sampling_interval == 0:
                count += 1
            count += int(tmp_node.end_time-tmp_node.start_time)/100 + 1
            #如果没有跨100，也就是说他们两个属于同一个100的时间片，那么减个1
            if int(tmp_node.end_time/100) == int(tmp_node.start_time/100):
                count -= 1

            tmp_node = tmp_node.next

    ratio = round(count/should_count,3) * 100

    #统计平均的运行时间占makespan比例
    unit_runtime_ratio = []
    for tll_name in TLL_dict:
        tll = TLL_dict[tll_name]
        unit_runtime_ratio.append(tll.allocate_list_total_time/max_allocate_time)

    avg_runtime_ratio = round((sum(unit_runtime_ratio)/len(unit_runtime_ratio))*100,1)

    return (max_allocate_time,round(float(avg_time)/len(task_list),2),hit_time,dirty_time,avg_runtime_ratio)

if __name__=="__main__":
    #generate_tasks(5)
    tasks = Tasks(task_list)
    tasks.fresh() #将任务中的状态值变为初始状态
    resource_fresh(resource) #将资源状态重置

    ret = alg(tasks,resource)
    print(ret)
